package Lagou.Stack;

import java.util.Stack;

/**
 * 例 3：找出数组中右边比我小的元素
 * 【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。
 * */
//单调栈
class Stack03 {
    public static int[] findRightSmall(int[] A) {
        //一个数总是想与左边比它大的数进行匹配，匹配到了之后，小的数会消除掉大的数。

        //结果数组
        int[] ans = new int[A.length];
        //栈中元素记录的是下标
        Stack<Integer> t = new Stack<>();
        for (int i = 0; i < A.length; i++) {
            final int x = A[i];
            //每个元素都向左遍历栈中元素完成消除动作
            while (!t.empty() && A[t.peek()] > x) {
                ans[t.peek()] = i;
                //值大的消失
                t.pop();
            }
            //剩下的入栈
            t.push(i);
        }
        // 栈中剩下的元素，由于没有人能消除他们，因此，只能将结果设置为-1。
        while (!t.empty()){
            ans[t.peek()] = -1;
            t.pop();
        }
        return ans;
    }
}
